#include "big_int.h"

big_int::big_int()
{
	shift = 0;
	digits = 0;
	sign = true;
};

big_int::big_int(std::string &str)
{
	sign = true;
	if (str[0] == '-')
	{
		sign = false;
		str = str.substr(1, str.length() - 1);
	}
	for (int i = str.length(); i > 0; i-= base_length)
	{
		if (i >= base_length)
		{
			digits.push_back(atoi(str.substr(i - base_length, base_length).c_str()));
		}
		else
		{
			digits.push_back(atoi(str.substr(0, i).c_str()));
		}
	}
	shift = 0;
};

big_int::big_int(long long n)
{
	sign = true;
	if (n < 0)
	{
		n = -n;
		sign = false;
	}
	if (n == 0)
	{
		digits.push_back(0);
	}
	while (n > 0)
	{
		digits.push_back(n % base);
		n /= base_length;
	}
	shift = 0;
};

big_int::big_int(const opt_vector& vect)
{
	if (vect.empty())
	{
		digits = opt_vector(1, 0);
	}
	else
	{
		digits = vect;
	}
	shift = 0;
	remove_zeroes();
};

big_int big_int::abs(const big_int& number)
{
	return (number < 0) ? - number : number;
};

void big_int::remove_zeroes()
{
	while ((digits.size() > 1) && (digits.back() == 0))
	{
		digits.pop_back();
	}
};

void big_int::restore()
{
	for (int i = 0; i < static_cast<int>(digits.size()); i++)
	{
		if (digits[i] >= 0)
		{
			long long tr = digits[i] / base;
			digits[i] %= base;
			if (tr > 0)
			{
				if (i < static_cast<int>(digits.size() - 1))
				{
					digits[i + 1] += tr;
				}
				else
				{
					digits.push_back(tr);
				}
			}
		}
		else
		{
			long long tr = - digits[i] / base;
			if (digits[i] % base != 0)
			{
				tr ++;
			}
			if (i < static_cast<int>(digits.size() - 1))
			{
				digits[i + 1] -= tr;
			}
			digits[i] += tr * base;
		}
	}
};

long long big_int::compare(const big_int &num) const
{
	if (sign && !num.sign)
		return 1;
	if (!sign && num.sign)
		return -1;

	int return_koef = 1;
	if (!sign && !num.sign)
		return_koef = -1;

	int temp = digits.size() - num.digits.size();
	if (shift + temp != num.shift)
		return return_koef * (temp + shift - num.shift);

	if (temp > 0)
	{
		int i = digits.size() - 1;
		while ((i > temp) && (digits[i] == num.digits[i - temp]))
			i--;
		if (i >= temp)
			return digits[i] - num.digits[i - temp];
		while (i >= 0)
		{
			if (digits[i] != 0)
				return return_koef;
			i--;
		}
	}
	else
	{
		int i = num.digits.size() - 1;
		while ((i > -temp) && (digits[i + temp] == num.digits[i]))
			i--;
		if (i >= -temp)
			return return_koef * (digits[i + temp] - num.digits[i]);
		while (i >= 0)
		{
			if (num.digits[i] != 0)
				return return_koef;
			i--;
		}
	}

	return 0;
};

//big_int& big_int::operator = (const big_int& number)
//{
//	digits = number.digits;
//	shift = number.shift;
//	sign = number.sign;
//	return *this;
//};


long long big_int::find_divider(const big_int& number)
{
	if (compare(number) < 0)
	{
		return 0;
	}
	int left = 0;
	int right = base;
	int middle;
	while (left != right - 1)
	{
		middle = (left + right) / 2;
		if (compare(number * middle) >= 0)
		{
			left = middle;
		}
		else
		{
			right = middle;
		}
	}
	return left;
};
 

int length(const int& number)
{
	if (number == 0)
		return 1;
	int num = number;
	int length_ = 0;
	while (num > 0) 
	{
		num /= 10;
		length_ ++;
	}
	return length_;
};
std::istream& operator >> (std::istream& is, big_int& number)
{
	std::string str;
	if (is >> str)
	{
		number = big_int(str);
	}
	return is;
};

std::ostream& operator << (std::ostream& os, big_int& number)
{
	if (!number.sign)
	{
		os << "-";
	}
	for (int i = number.digits.size() - 1; i >= 0; i--)
	{
		int zero = big_int::base_length - length(static_cast<int>(number.digits[i]));
		if (i < static_cast<int>(number.digits.size() - 1))
		{
			for (int j = 0; j < zero; j++)
			{
				os << '0'; 
			}
		}
		os << number.digits[i];
	}
	return os;
};

bool big_int::operator < (const big_int& num) const
{
	return compare(num) < 0;
};

bool big_int::operator > (const big_int& num) const
{
	return compare(num) > 0;
};

bool big_int::operator <= (const big_int& num) const
{
	return compare(num) <= 0;
};

bool big_int::operator >= (const big_int& num) const
{
	return compare(num) >= 0;
};

bool big_int::operator == (const big_int& num) const
{
	return compare(num) == 0;
};

bool big_int::operator != (const big_int& num) const
{
	return compare(num) != 0;
};

big_int big_int::operator -() const
{
	big_int temp = *this;
	temp.sign = !temp.sign;
	return temp;
};


big_int& big_int::operator += (const big_int& num)  
{
	big_int first = *this;
	big_int second = num;

	big_int res;
	res.digits.resize(0);

	long long m = std::min(first.shift, second.shift);
	long long len = std::max(first.digits.size() + first.shift, second.digits.size() + second.shift) - m;
	int sign_1 = first.sign ? 1 : -1;
	int sign_2 = second.sign ? 1 : -1;
	long long tmp = 0;
	for (int i = 0; i < len; i++)
	{
		long long sum = tmp;
		if ((i + m >= first.shift) && (i + m < first.shift + first.digits.size()))
		{
			sum += sign_1 * first.digits[i + static_cast<int>(m - first.shift)];
		}
		if ((i + m >= second.shift) && (i + m < second.shift + second.digits.size()))
		{
			sum += sign_2 * first.digits[i + static_cast<int>(m - second.shift)];
		}
		tmp = 0;
		if (abs(sum) > base)
		{
			tmp = sum / base;
			sum %= base;
		}
		if (sum < 0)
		{
			tmp = -1;
			sum += base;
		}
		digits.push_back(sum);
	}
	remove_zeroes();
	return *this;
};

big_int& big_int::operator -= (const big_int& num)
{
		return *this += -num;
};

big_int& big_int::operator *= (const big_int& num)
{
	big_int first = *this;
	big_int second = num;
	if ((*this == 0) || (num == 0))
	{
		*this = 0;
		return *this;
	}

	if ((sign && num.sign) || (!sign && !num.sign))
	{
		sign = true;
	}
	else if ((sign && !num.sign) || (!sign && num.sign))
	{
		sign = false;
	}

	digits = opt_vector(first.digits.size() + second.digits.size() + 1, 0);

	for (int i = 0; i < first.digits.size(); i++)
	{
		long long tmp = 0;
		for (int j = 0; j < second.digits.size(); j++)
		{
			long long mp = first.digits[i] * second.digits[j];
			digits[i + j] += tmp + mp % base;
			tmp = (mp + digits[i + j]) / base;
			digits[i + j] %= base;
		}
		digits[i + second.digits.size()] += tmp;
		tmp = digits[i + second.digits.size()] / base;
		digits[i + second.digits.size()] %= base;
		digits[i + second.digits.size() + 1] = tmp;
	}
	remove_zeroes();
	return *this;
};

std::pair <big_int, big_int> big_int::division(const big_int& number) 
{
	big_int first = *this;
	big_int second = number;

	if (abs(first) < abs(second))
	{
		return std::make_pair(big_int(0), first);
	}
	if ((sign && number.sign) || (!sign && !number.sign))
	{
		sign = true;
	}
	else if ((sign && !number.sign) || (!sign && number.sign))
	{
		sign = false;
	}

	opt_vector quotient;

	int tmp = first.digits.size() - second.digits.size();
	second.shift += tmp;
	while (compare(second) >= 0)
	{
		long long temp = find_divider(second);
		quotient.push_back(temp);
		*this -= second * static_cast<int>(temp);
		second.shift--;
	}
	quotient.reverse();

	if (second.shift >= 0)
	{
		quotient.insert(quotient.begin(), static_cast<int>(second.shift) + 1, long long(0));
	}
	big_int res(quotient);
	res.sign = sign;
	return std::make_pair(res, *this);
};

big_int& big_int::operator /= (const big_int& num)
{
	*this = division(num).first;
	return *this;
};

big_int& big_int::operator %= (const big_int& num)
{
	*this = division(num).second;
	return *this;
};

big_int big_int::operator + (const big_int& num) const
{
	big_int tmp = *this;
	tmp += num;
	return tmp;
};

big_int big_int::operator - (const big_int& num) const
{
	big_int tmp = *this;
	tmp -= num;
	return tmp;
};

big_int big_int::operator * (const big_int& num) const
{
	big_int tmp = *this;
	tmp *= num;
	return tmp;
};

big_int big_int::operator / (const big_int& num) const
{
	big_int tmp = *this;
	tmp /= num;
	return tmp;
};

big_int big_int::operator % (const big_int& num) const
{
	big_int tmp = *this;
	tmp %= num;
	return tmp;
};